package com.example.demo;

import java.util.PriorityQueue;
import java.util.Queue;

public class MedianFinder {
    Queue<Integer> min;
    Queue<Integer> max;
    public MedianFinder() {
        max=new PriorityQueue<Integer>(
            (first,second)->{
                return first.compareTo(second);
            }
        );
        min=new PriorityQueue<Integer>(
            (first,second)->{
                return second.compareTo(first);
            }
        );
    }
    
    public void addNum(int num) {
        if(min.isEmpty()||num<=min.peek()){
            min.offer(num);
            if(max.size()+1<min.size()){
                max.offer(min.poll());
            }
        }else{
            max.offer(num);
            if(min.size()<max.size()){
                min.offer(max.poll());
            }
        }
    }
    
    public double findMedian() {
        if(max.size()==min.size()){
            return (max.peek()+min.peek())/2.0;
        }
        return min.peek();
    }
}
